1. Field of the Invention
The present invention relates to a parallel processing Reed-Solomon encoding circuit, and more particularly to the error correction for any number (two or more) of blocks.
2. Description of the Related Art
Conventionally, a Reed-Solomon encoder has been well known which employs a method of a polynomial dividing circuit of shift register type as described in “Error Correction Encoding Techniques” supervised by Hideki Imai, Japan Engineering Technology Center, 1986), p.30 (hereinafter referred to as a document 1). However, this method does not allow the circuit to be operated at high rate, and is unsuitable for the Reed-Solomon encoding circuit that requires a high throughput as with an optical communication system of high speed and large capacity.
As the Reed-Solomon encoding circuit for realizing the high throughput, a system for making the parallel processing of polynomial division was proposed in Japanese Patent Laid-Open No. 11-136136 (hereinafter referred to as a document 2). To explain the system as proposed in this document 2, for example, an encoder is considered which produces an encoded signal of the code length of 16 bytes by appending a redundancy check signal of 4 bytes to an information signal of 12 bytes.
In this case, a signal of one byte can be converted into an element of a Galois field consisting of 256 elements, and vice versa. It is supposed that a primitive polynomial of the Galois field is x8+x4+x3+x2+1, and a primitive element is α. An eleventh order information polynomial I(x) is considered having the coefficients consisting of information series (I11, I10, . . . , I0) with an information signal of 12 bytes converted into the Galois field.
From the product of I(x) and x4 and the generator polynomial G(x), a third order check polynomial P(x) is obtained such as;P(x)=I (x)x4 mod G(x)  (1)G(x)=(x−α)(x−α2) . . . (x−α4)  (2)
The check polynomial P(x) is a remainder from I(x) x4 divided by the fourth order generator polynomial G(x). The coefficients (P3, . . . , P0) of this fourth order check polynomial P(x) are 4 bytes of the redundancy check signal. The encoded signal consists of the information signal of 12 bytes followed by the redundancy check signal of 4 bytes.
Herein, a case is considered in which when the signal is processed 2 bytes in parallel, for example, the division is made by the second order coefficient at a time. The coefficient of a Galois field multiplier portion within a parallel polynomial divider is obtained by the following transformation:I(x)x4=Σi  (3) G(x)=Σgixi  (4)Where Σ in an expression (3) denotes a sum for i=4 to 15, and Σ in an expression (4) denotes a sum for i=0 to 4.
In the above expression, let G(x)=0. Then,x4=Σgixi  (5)Substituting this into I(x) x4 in succession, the remainder P(x) can be obtained. Where Σ in an expression (5) denotes a sum for i=0 to 3.
From the expression (5),                                                                                                               I                    ⁡                                          (                      x                      )                                                        ⁢                                      x                    4                                                  =                                ⁢                                                                            α                      15                                        ⁢                                          x                      11                                        ⁢                    Σ                    ⁢                                                                                   ⁢                    a                    ⁢                                                                                   ⁢                                          g                      i                                        ⁢                                          x                      i                                                        +                                                            Σ                      b                                        ⁢                                          α                      i                                        ⁢                                          x                      i                                                                                                                                              =                                ⁢                                                                            α                      15                                        ⁢                                          Σ                      a                                        ⁢                                          g                      i                                        ⁢                                          x                                              i                        +                        11                                                                              +                                                            Σ                      b                                        ⁢                                          α                      i                                        ⁢                                          x                      i                                                                                                                                              =                                ⁢                                                                            α                      15                                        ⁢                                          g                      3                                        ⁢                                          x                      14                                                        +                                                            α                      15                                        ⁢                                          Σ                      c                                        ⁢                                          g                      i                                        ⁢                                          x                                              i                        +                        11                                                                              +                                                            Σ                      b                                        ⁢                                          α                      i                                        ⁢                                          x                      i                                                                                                                                              =                                ⁢                                                                            α                      15                                        ⁢                                          g                      3                                        ⁢                                          Σ                      a                                        ⁢                                          g                      i                                        ⁢                                          x                                              i                        +                        10                                                                              +                                                            α                      15                                        ⁢                                          Σ                      c                                        ⁢                                          g                                              i                        -                        1                                                              ⁢                                          x                                              i                        +                        10                                                                              +                                                            Σ                      b                                        ⁢                                          α                      i                                        ⁢                                          x                      i                                                                                                                                              =                                ⁢                                                                            Σ                      a                                        ⁢                                                                  α                        15                                            ⁡                                              (                                                                                                            g                              3                                                        ⁢                                                          g                              i                                                                                +                                                      g                                                          i                              -                              1                                                                                                      )                                                              ⁢                                          x                                              i                        +                        10                                                                              +                                                            Σ                      b                                        ⁢                                          α                      i                                        ⁢                                          x                      i                                                                                                                                              =                                ⁢                                                                            Σ                      a                                        ⁢                                                                  α                        15                                            ⁡                                              (                                                                                                            g                              3                                                        ⁢                                                          g                              i                                                                                +                                                      g                                                          i                              -                              1                                                                                                      )                                                              ⁢                                          x                                              i                        +                        10                                                                              +                                                            α                      14                                        ⁢                                          Σ                      a                                        ⁢                                          g                      i                                        ⁢                                          x                                              i                        +                        10                                                                              +                                                            Σ                      d                                        ⁢                                          α                      i                                        ⁢                                          x                      i                                                                                                                                              =                                ⁢                                                                            Σ                      a                                        ⁢                                          {                                                                                                    α                            15                                                    ⁡                                                      (                                                                                                                            g                                  3                                                                ⁢                                                                  g                                  i                                                                                            +                                                              g                                                                  i                                  -                                  1                                                                                                                      )                                                                          +                                                                              g                            i                                                    ⁢                                                      α                            14                                                                                              }                                        ⁢                                          x                                              i                        +                        10                                                                              +                                                            Σ                      d                                        ⁢                                          α                      i                                        ⁢                                          x                      i                                                                                                          ⁢                                  ⁢                  (                      herein            ,                                                   ⁢                                          g                                  -                  1                                            =              0                                )                                    (        6        )            Where Σa denotes a sum for i=0 to 3, Σb denotes a sum for i=4 to 14, Σc denotes a sum for i=0 to 2, and Σd denotes a sum for i=4 to 13.
Herein, if hi is defined ashi=g3gi+gi−1  (7)an expression (6) is written such asI(x)x4=Σa{α15hi+α14gi}xi+10+Σdαixi  (8)
In this way, the order of input data is decreased by two at a time. That is, this corresponds to the summation of the two-byte input data multiplied by g and h, and the next input value. This operation is repeated until the order is equal to 3, so that the check polynomial P(x) can be obtained.
Then, hi, for example, can be simply calculated from the coefficient of the polynomial of the remainder from x5 divided by G(x). If the same operation as above is performed, a circuit configuration for processing M bytes simultaneously can be considered.
FIG. 6 is a block diagram of the above example. Referring to FIG. 6, a 16-bit signal and a clock at the same rate as the signal are input in parallel, the 16-bit signal being processed in a unit of one byte.
A two-byte signal is branched into two, a first byte is entered into the first input of a first selector circuit 202 and the first input of a first exclusive-OR circuit 204. Similarly, a second byte is entered into the first input of a second selector circuit 203 and the first input of a second exclusive-OR circuit 205. At this time, those signals are defined as A and B, respectively.
Each of the outputs from the first exclusive-OR circuit 204 and the second exclusive-OR circuit 205 is branched into four, wherein an output from the second exclusive-OR circuit 205 is entered into a first Galois field multiplier circuit 206, a second Galois field multiplier circuit 207, a third Galois field multiplier circuit 208, and a fourth Galois field multiplier circuit 209, and an output from the first exclusive-OR circuit 204 is entered into a fifth Galois field multiplier circuit 210, a sixth Galois field multiplier circuit 211, a seventh Galois field multiplier circuit 212, and an eighth Galois field multiplier circuit 213.
The multiplier factors of the first Galois field multiplier circuit 206, the second Galois field multiplier circuit 207, the third Galois field multiplier circuit 208, and the fourth Galois field multiplier circuit 209 are calculated from the coefficients of the generator polynomial G(x), those coefficients being α10, α81, α251 and α76, respectively.
Also, the multiplier factors of the fifth Galois field multiplier circuit 210, the sixth Galois field multiplier circuit 211, the seventh Galois field multiplier circuit 212, and the eighth Galois field multiplier circuit 213 are calculated from the remainder from x5divided by the generator polynomial G(x), those coefficients being α86, α63, α192 and α166, respectively. The outputs from the first Galois field multiplier circuit 206 and the fifth Galois field multiplier circuit 210 are exclusive-ORed in the third exclusive-OR circuit 214, and entered into a first D-F/F (D-flip-flop) 220.
The output of the first D-F/F 220, the output of the second Galois field multiplier circuit 207, and the output of the sixth Galois field multiplier circuit 211 are exclusive-ORed in the fourth exclusive-OR circuit 215 and the fifth exclusive-OR circuit 216, and entered into a second D-F/F 221.
Further, the output of the third Galois field multiplier circuit 208, and the output of the seventh Galois field multiplier circuit 212 are exclusive-ORed in the sixth exclusive-OR circuit 217, and entered into a third D-F/F 222. The output of the third D-F/F 222, the output of the fourth Galois field multiplier circuit 209, and the output of the eighth Galois field multiplier circuit 213 are exclusive-ORed in the seventh exclusive-OR circuit 218 and the eighth exclusive-OR circuit 219, and entered into a fourth D-F/F 223.
The output of the second D-F/F 221 is branched into two, one being entered into the second input of the first exclusive-OR circuit 204, and the other being entered into the first selector circuit 202. At this time, a signal entered into the first selector circuit 202 is designated as a signal C. Also, the output of the fourth D-F/F 223 is branched into two, one being entered into the second input of the second exclusive-OR circuit 205, and the other being entered into the second selector circuit 203. At this time, a signal entered into the second selector circuit 205 is designated as a signal D. A clock is input into the first D-F/F 220, the second D-F/F 221, the third D-F/F 222 and the fourth D-F/F 223, and a counter 201.
The first selector circuit 202 and the second selector circuit 203 select a signal depending on the value of the counter 201. The counter 201 is reset in accordance with the initial location of a frame format, the counter value being reset to be zero at every eight clocks.
In this example, if the value of the counter 201 is from 0 to 5, the signals A and B are selected, and if the value of the counter 201 is from 6 to 7, the signals C and D are selected. By adopting the above circuit configuration, a two-byte correctable (16, 12) Reed-Solomon encoding circuit can be configured. Since the use of such configuration allows two bytes to be processed at the same time, the same throughput of the polynomial dividing circuit of shift register type as described in the document 1 p.30 can be obtained with a half clock rate.
The above example is involved in the case where the code length N is divisible by the parallel processing number M. When the code length N is indivisible by the parallel processing number M, it is common that an initial auxiliary signal of the minimum natural number L where (N+L) is divisible by M is appended to the initial location of the information signal as described in the second example of the document 2.
In the conventional Reed-Solomon encoder as described above, the M D-F/F outputs in which the highest (K−1)th order to the (K−M)th order coefficients are preserved and the input signal are exclusive-ORed and entered into the Galois field multiplier circuit. This corresponds to a multiplication of the input signal by xK.
Accordingly, the coefficient preserved in the D-F/F when the information signal I(x) is all input is a remainder from I(x) xK divided by the generator polynomial G(x), namely, a check signal P(x). Since M blocks are entered every time, the parallel processing number M is required to be a divisor of the input signal length N−K+L which is the sum of the lengths of the information signal and the initial auxiliary signal. Since the parallel processing number M is a divisor of N+L, it is required that the parallel processing number M may be a divisor of the redundancy check length K. Hence, there is a problem that arbitrary parallel processing number may not be taken. More specifically, the parallel processing number M must be a divisor of the redundancy check length K.